Internet traffic increases by a factor of 10 every year while the number of hosts on the Internet increases by a factor of 3 every 2 years. This means that in order to maintain the same performance levels, packets now need to be forwarded faster despite there being a larger forwarding database. Larger databases increase the number of memory accesses required to determine the address of the next node to which a packet is to be forwarded. Such an address is commonly referred to as a next hop address.
In order to meet the demands of high-speed routing, such as gigabit or terabit routing, it is desirable that address lookups be performed in hardware. Currently, the fastest software approaches still take hundreds of nanoseconds on average in order to perform address lookups, which is unsuitable for such high-speed forwarding.
The lookup to determine the next hop address of a packet is the most time critical part in packet forwarding. The problem of searching in large databases is compounded by the fact that routing tables store variable length prefixes and their corresponding next hop addresses. In order to forward a packet, routers need to find the longest prefix in the routing table that matches the destination address in a packet to be forwarded.
A number of approaches have been developed to search for longest matching prefixes. Most approaches fall under the category of search trees. In conventional search trees, each bit in the address of a received packet is used to determine a path through the tree. A ‘0’ points to the left half of a sub-tree within the tree and a ‘1’ points to the right half of a sub-tree within the tree. The lookup proceeds by traversing the tree until a leaf node is located. The tree data structure includes nodes that store pointers to child nodes. All leaf nodes and some internal nodes contain next hop information. Some implementations require only leaf nodes to store next hop information in which case the internal nodes store only pointers to child nodes.
In most conventional implementations, the entire tree structure that includes the next hop addresses is stored in one memory. As routing tables become larger, such data structures will not fit entirely in on-chip memories. As a result, off-chip memory accesses are required. Because multiple off-chip memory accesses are required, the goals of fast and constant network address lookups cannot be achieved.
Thus, a need still remains for network communication system with packet forwarding. In view of the exploding usage of the Internet and the availability of on-line information, it is increasingly critical that answers be found to these problems. In view of the ever-increasing commercial competitive pressures, along with growing consumer expectations and the diminishing opportunities for meaningful product differentiation in the marketplace, it is critical that answers be found for these problems. Additionally, the need to reduce costs, improve efficiencies and performance, and meet competitive pressures adds an even greater urgency to the critical necessity for finding answers to these problems.
Solutions to these problems have been long sought but prior developments have not taught or suggested any solutions and, thus, solutions to these problems have long eluded those skilled in the art.